package Backtracking;

import java.util.Arrays;

public class 解数独 {

    boolean[][] row = new boolean[9][10];
    boolean[][] col = new boolean[9][10];
    boolean[][] matrix = new boolean[9][10];
    char[][] board;

    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int num = c - '0';
                    row[i][num] = true;
                    col[j][num] = true;
                    matrix[3 * (i / 3) + (j / 3)][num] = true;
                }
            }
        }
        backTracking(0);
    }

    private boolean backTracking(int n) {
        if (n == 81) return true;
        int i = n / 9;
        int j = n % 9;
        if (board[i][j] != '.') return backTracking(n + 1);
        for (int num = 1; num <= 9; num++) {
            if (row[i][num] || col[j][num] || matrix[3 * (i / 3) + (j / 3)][num]) continue;
            board[i][j] = (char) ('0' + num);
            row[i][num] = true;
            col[j][num] = true;
            matrix[3 * (i / 3) + (j / 3)][num] = true;
            if (backTracking(n + 1)) return true;
            board[i][j] = '.';
            row[i][num] = false;
            col[j][num] = false;
            matrix[3 * (i / 3) + (j / 3)][num] = false;
        }
        return false;
    }

    public static void main(String[] args) {
        解数独 test = new 解数独();
        char[][] sudoku = new char[][]{
                        {'.','.','6','.','.','.','.','.','1'},
                        {'.','3','.','.','.','.','8','.','.'},
                        {'.','.','.','5','.','8','4','.','.'},
                        {'.','6','.','.','1','.','.','2','.'},
                        {'.','.','3','.','.','7','.','.','.'},
                        {'.','9','1','.','.','.','3','.','.'},
                        {'.','.','.','.','.','5','1','7','.'},
                        {'1','5','.','.','2','6','.','.','.'},
                        {'.','.','.','.','9','.','6','5','.'}};
        test.solveSudoku(sudoku);
        System.out.println(Arrays.deepToString(sudoku));
    }
}
